//package binaryTree;
//
//
//import java.util.LinkedList;
//
//
////二叉树  深度 高度的那些概念
//
//public class FindtheValLeftRootCorner {
////    public int findBottomLeftValue(TreeNode root) {
////        LinkedList<TreeNode> list = new LinkedList<>();
////        if (root!=null){
////            list.add(root);
////        }
////        while (!list.isEmpty()) {
////            int size = list.size();
////            while (size > 0) {
////                TreeNode cur = list.poll();
////                if (cur.left!=null){
////                    list.add(cur.left);
////                }
////                if (cur.right!=null){
////                    list.add(cur.right);
////                }
////                size--;
////            }
////        }
////
////   return 0;
////
////    }
////
////
////
////    public int maxDepth(TreeNode root) {
////        int maxDepth=0;
////        LinkedList<TreeNode> list = new LinkedList<>();
////        if (root!=null){
////            list.add(root);
////        }
////        while (!list.isEmpty()) {
////            maxDepth++;
////            int size = list.size();
////            while (size > 0) {
////               TreeNode cur = list.poll();
////                if (cur.left!=null){
////                    list.add(cur.left);
////                }
////                if (cur.right!=null){
////                    list.add(cur.right);
////                }
////                size--;
////            }
////        }
////        return  maxDepth;
////    }
//
//    //TODO:我自己实现的　　先找出深度　然后再层序遍历找　左下角的数值
//    public int findBottomLeftValue(TreeNode root) {
//        int res=0;
//        int depth = maxDepth(root);
//        LinkedList<TreeNode> list = new LinkedList<>();
//        if (root==null){
//            return 0;
//        }
//        list.add(root);
//        int curDepth=0;
//        while (!list.isEmpty()){
//            curDepth++;
//            int size = list.size();
//            while (size>0){
//                TreeNode cur = list.poll();
//                if (curDepth==depth){
//                    res=cur.val;
//              break;
//
//                }
//
//                if (cur.left!=null){
//                    list.add(cur.left);
//                }
//                if (cur.right!=null){
//                    list.add(cur.right);
//                }
//                size--;
//            }
//        }
//        return  res;
//    }
//
//    public  int maxDepth(TreeNode  root){
//        if (root==null){
//            return 0;
//        }
//        int leftDepth = maxDepth(root.left);
//        int rightDepth = maxDepth(root.right);
//        return  1+Math.max(leftDepth,rightDepth);
//    }
//
//
//    //todo:递归实现
//
//    private int Deep = -1;
//    private int value = 0;
//    public int findBottomLeftValue1(TreeNode root) {
//        value = root.val;
//        findLeftValue(root,0);
//        return value;
//    }
//
//    private void findLeftValue (TreeNode root,int deep) {
//        if (root == null) return;
//        if (root.left == null && root.right == null) {
//            //因为是前序遍历所以保证了最后一层的第一个遍历到的一定是左下角第一个节点
//            if (deep > Deep) {
//                value = root.val;
//                Deep = deep;
//            }
//        }
//        if (root.left != null) findLeftValue(root.left,deep + 1);
//        if (root.right != null) findLeftValue(root.right,deep + 1);
//    }
//
//    public static void main(String[] args) {
//        TreeNode treeNode1 = new TreeNode(2);
//        TreeNode treeNode2 = new TreeNode(1);
//        TreeNode treeNode3 = new TreeNode(3);
//        treeNode1.left=treeNode2;
//        treeNode1.right=treeNode3;
//        FindtheValLeftRootCorner findtheValLeftRootCorner = new FindtheValLeftRootCorner();
//        int bottomLeftValue = findtheValLeftRootCorner.findBottomLeftValue1(treeNode1);
//        System.out.println(bottomLeftValue);
//
//
//    }
//
//}
